home *** CD-ROM | disk | FTP | other *** search
/ The Atari Compendium / The Atari Compendium (Toad Computers) (1994).iso / files / prgtools / mint / shells / tcshsrc.zoo / tcsh / tc.alloc.c < prev    next >
Encoding:
C/C++ Source or Header  |  1992-02-01  |  15.1 KB  |  585 lines
  1. /* $Header: /tmp_mnt/home/ragmanns/mu/christos/src/sys/tcsh-6.00/RCS/tc.alloc.c,v 3.3 91/07/19 01:31:14 christos Exp $ */
  2. /*
  3.  * tc.alloc.c (Caltech) 2/21/82
  4.  * Chris Kingsley, kingsley@cit-20.
  5.  *
  6.  * This is a very fast storage allocator.  It allocates blocks of a small
  7.  * number of different sizes, and keeps free lists of each size.  Blocks that
  8.  * don't exactly fit are passed up to the next larger size.  In this
  9.  * implementation, the available sizes are 2^n-4 (or 2^n-12) bytes long.
  10.  * This is designed for use in a program that uses vast quantities of memory,
  11.  * but bombs when it runs out.
  12.  */
  13. /*-
  14.  * Copyright (c) 1980, 1991 The Regents of the University of California.
  15.  * All rights reserved.
  16.  *
  17.  * Redistribution and use in source and binary forms, with or without
  18.  * modification, are permitted provided that the following conditions
  19.  * are met:
  20.  * 1. Redistributions of source code must retain the above copyright
  21.  *    notice, this list of conditions and the following disclaimer.
  22.  * 2. Redistributions in binary form must reproduce the above copyright
  23.  *    notice, this list of conditions and the following disclaimer in the
  24.  *    documentation and/or other materials provided with the distribution.
  25.  * 3. All advertising materials mentioning features or use of this software
  26.  *    must display the following acknowledgement:
  27.  *    This product includes software developed by the University of
  28.  *    California, Berkeley and its contributors.
  29.  * 4. Neither the name of the University nor the names of its contributors
  30.  *    may be used to endorse or promote products derived from this software
  31.  *    without specific prior written permission.
  32.  *
  33.  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  34.  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  35.  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  36.  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  37.  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  38.  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  39.  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  40.  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  41.  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  42.  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  43.  * SUCH DAMAGE.
  44.  */
  45. #include "config.h"
  46. RCSID("$Id: tc.alloc.c,v 3.3 91/07/19 01:31:14 christos Exp $")
  47.  
  48.  
  49. #include "sh.h"
  50.  
  51. #ifdef __MINT__
  52. long _stksize = -128*1024L;
  53. #endif /* __MINT__ */
  54.  
  55. char   *memtop = NULL;        /* PWP: top of current memory */
  56. char   *membot = NULL;        /* PWP: bottom of allocatable memory */
  57.  
  58. #ifndef SYSMALLOC
  59.  
  60. #undef RCHECK
  61. #undef DEBUG
  62.  
  63.  
  64. #ifndef NULL
  65. #define    NULL 0
  66. #endif
  67.  
  68. typedef unsigned char U_char;    /* we don't really have signed chars */
  69. typedef unsigned int U_int;
  70. typedef unsigned short U_short;
  71.  
  72.  
  73. /*
  74.  * The overhead on a block is at least 4 bytes.  When free, this space
  75.  * contains a pointer to the next free block, and the bottom two bits must
  76.  * be zero.  When in use, the first byte is set to MAGIC, and the second
  77.  * byte is the size index.  The remaining bytes are for alignment.
  78.  * If range checking is enabled and the size of the block fits
  79.  * in two bytes, then the top two bytes hold the size of the requested block
  80.  * plus the range checking words, and the header word MINUS ONE.
  81.  */
  82.  
  83.  
  84. #define MEMALIGN(a) (((a) + ROUNDUP) & ~ROUNDUP)
  85.  
  86. union overhead {
  87.     union overhead *ov_next;    /* when free */
  88.     struct {
  89.     U_char  ovu_magic;    /* magic number */
  90.     U_char  ovu_index;    /* bucket # */
  91. #ifdef RCHECK
  92.     U_short ovu_size;    /* actual block size */
  93.     U_int   ovu_rmagic;    /* range magic number */
  94. #endif
  95.     }       ovu;
  96. #define    ov_magic    ovu.ovu_magic
  97. #define    ov_index    ovu.ovu_index
  98. #define    ov_size        ovu.ovu_size
  99. #define    ov_rmagic    ovu.ovu_rmagic
  100. };
  101.  
  102. #define    MAGIC        0xfd    /* magic # on accounting info */
  103. #define RMAGIC        0x55555555    /* magic # on range info */
  104. #ifdef RCHECK
  105. #define    RSLOP        sizeof (U_int)
  106. #else
  107. #define    RSLOP        0
  108. #endif
  109.  
  110.  
  111. #define ROUNDUP    7
  112.  
  113. /*
  114.  * nextf[i] is the pointer to the next free block of size 2^(i+3).  The
  115.  * smallest allocatable block is 8 bytes.  The overhead information
  116.  * precedes the data area returned to the user.
  117.  */
  118. #define    NBUCKETS 30
  119. static union overhead *nextf[NBUCKETS];
  120.  
  121. #ifdef notdef
  122. extern char *sbrk();
  123.  
  124. #endif
  125.  
  126. /*
  127.  * nmalloc[i] is the difference between the number of mallocs and frees
  128.  * for a given block size.
  129.  */
  130. static U_int nmalloc[NBUCKETS];
  131.  
  132. static    int    findbucket    __P((union overhead *, int));
  133. static    void    morecore    __P((int));
  134.  
  135.  
  136. #ifdef DEBUG
  137. #define CHECK(a, str, p) \
  138.     if (a) { \
  139.     xprintf(str, p);    \
  140.     xprintf("memtop = %lx membot = %lx.\n", memtop, membot);    \
  141.     abort(); \
  142.     }    \
  143.     else
  144. #else
  145. #define CHECK(a, str, p) \
  146.     if (a) { \
  147.     xprintf(str, p);    \
  148.     xprintf("memtop = %lx membot = %lx.\n", memtop, membot);    \
  149.     return; \
  150.     }    \
  151.     else
  152. #endif
  153.  
  154. memalign_t
  155. malloc(nbytes)
  156.     register size_t nbytes;
  157. {
  158. #ifndef lint
  159.     register union overhead *p;
  160.     register int bucket = 0;
  161.     register unsigned shiftr;
  162.  
  163.     /*
  164.      * Convert amount of memory requested into closest block size stored in
  165.      * hash buckets which satisfies request.  Account for space used per block
  166.      * for accounting.
  167.      */
  168. #ifdef SUNOS4
  169.     /*
  170.      * SunOS localtime() overwrites the 9th byte on an 8 byte malloc()....
  171.      * so we get one more...
  172.      */
  173.     if (nbytes == 8) nbytes++;
  174. #endif
  175.  
  176.     nbytes = MEMALIGN(MEMALIGN(sizeof(union overhead)) + nbytes + RSLOP);
  177.     shiftr = (nbytes - 1) >> 2;
  178.  
  179.     /* apart from this loop, this is O(1) */
  180.     while (shiftr >>= 1)
  181.     bucket++;
  182.     /*
  183.      * If nothing in hash bucket right now, request more memory from the
  184.      * system.
  185.      */
  186.     if (nextf[bucket] == NULL)
  187.     morecore(bucket);
  188.     if ((p = (union overhead *) nextf[bucket]) == NULL) {
  189.     child++;
  190. #ifndef DEBUG
  191.     stderror(ERR_NOMEM);
  192. #else
  193.     showall(NULL, NULL);
  194.     xprintf("nbytes=%d: Out of memory\n", nbytes);
  195.     abort();
  196. #endif
  197.     /* fool lint */
  198.     return ((memalign_t) 0);
  199.     }
  200.     /* remove from linked list */
  201.     nextf[bucket] = nextf[bucket]->ov_next;
  202.     p->ov_magic = MAGIC;
  203.     p->ov_index = bucket;
  204.     nmalloc[bucket]++;
  205. #ifdef RCHECK
  206.     /*
  207.      * Record allocated size of block and bound space with magic numbers.
  208.      */
  209.     if (nbytes <= 0x10000)
  210.     p->ov_size = nbytes - 1;
  211.     p->ov_rmagic = RMAGIC;
  212.     *((U_int *) (((caddr_t) p) + nbytes - RSLOP)) = RMAGIC;
  213. #endif
  214.     return ((memalign_t) (((caddr_t) p) + MEMALIGN(sizeof(union overhead))));
  215. #else
  216.     if (nbytes)
  217.     return ((memalign_t) 0);
  218.     else
  219.     return ((memalign_t) 0);
  220. #endif                /* !lint */
  221. }
  222.  
  223. #ifndef lint
  224. /*
  225.  * Allocate more memory to the indicated bucket.
  226.  */
  227. static void
  228. morecore(bucket)
  229.     register bucket;
  230. {
  231.     register union overhead *op;
  232.     register int rnu;        /* 2^rnu bytes will be requested */
  233.     register int nblks;        /* become nblks blocks of the desired size */
  234.     register int siz;
  235.  
  236.     if (nextf[bucket])
  237.     return;
  238.     /*
  239.      * Insure memory is allocated on a page boundary.  Should make getpageize
  240.      * call?
  241.      */
  242.     op = (union overhead *) sbrk(0);
  243.     memtop = (char *) op;
  244.     if (membot == NULL)
  245.     membot = memtop;
  246.  
  247. #ifndef __MINT__
  248.     if ((int) op & 0x3ff) {
  249.     memtop = (char *) sbrk(1024 - ((int) op & 0x3ff));
  250.     memtop += 1024 - ((int) op & 0x3ff);
  251.     }
  252. #endif
  253.  
  254.     /* take 2k unless the block is bigger than that */
  255.     rnu = (bucket <= 8) ? 11 : bucket + 3;
  256.     nblks = 1 << (rnu - (bucket + 3));    /* how many blocks to get */
  257.     if (rnu < bucket)
  258.     rnu = bucket;
  259.     memtop = (char *) sbrk(1 << rnu);    /* PWP */
  260.     op = (union overhead *) memtop;
  261.     memtop += 1 << rnu;
  262.     /* no more room! */
  263.     if ((int) op == -1)
  264.     return;
  265.     /*
  266.      * Round up to minimum allocation size boundary and deduct from block count
  267.      * to reflect.
  268.      */
  269.     if (((U_int) op) & ROUNDUP) {
  270.     op = (union overhead *) (((U_int) op + (ROUNDUP + 1)) & ~ROUNDUP);
  271.     nblks--;
  272.     }
  273.     /*
  274.      * Add new memory allocated to that on free list for this hash bucket.
  275.      */
  276.     nextf[bucket] = op;
  277.     siz = 1 << (bucket + 3);
  278.     while (--nblks > 0) {
  279.     op->ov_next = (union overhead *) (((caddr_t) op) + siz);
  280.     op = (union overhead *) (((caddr_t) op) + siz);
  281.     }
  282. #ifdef __MINT__
  283.    op->ov_next = 0;
  284. #endif
  285. }
  286.  
  287. #endif
  288.  
  289. void
  290. free(cp)
  291.     ptr_t   cp;
  292. {
  293. #ifndef lint
  294.     register int size;
  295.     register union overhead *op;
  296.  
  297.     if (cp == NULL)
  298.     return;
  299.     CHECK(!memtop || !membot, "free(%lx) called before any allocations.", cp);
  300.     CHECK(cp > (ptr_t) memtop, "free(%lx) above top of memory.", cp);
  301.     CHECK(cp < (ptr_t) membot, "free(%lx) below bottom of memory.", cp);
  302.     op = (union overhead *) (((caddr_t) cp) - MEMALIGN(sizeof(union overhead)));
  303.     CHECK(op->ov_magic != MAGIC, "free(%lx) bad block.", cp);
  304.  
  305. #ifdef RCHECK
  306.     if (op->ov_index <= 13)
  307.     CHECK(*(U_int *) ((caddr_t) op + op->ov_size + 1 - RSLOP) != RMAGIC,
  308.           "free(%lx) bad range check.", cp);
  309. #endif
  310.     CHECK(op->ov_index >= NBUCKETS, "free(%lx) bad block index.", cp);
  311.     size = op->ov_index;
  312.     op->ov_next = nextf[size];
  313.     nextf[size] = op;
  314.  
  315.     nmalloc[size]--;
  316.  
  317. #else
  318.     if (cp == NULL)
  319.     return;
  320. #endif
  321. }
  322.  
  323. memalign_t
  324. calloc(i, j)
  325.     size_t  i, j;
  326. {
  327. #ifndef lint
  328.     register char *cp, *scp;
  329.  
  330.     i *= j;
  331.     scp = cp = (char *) xmalloc((size_t) i);
  332.     if (i != 0)
  333.     do
  334.         *cp++ = 0;
  335.     while (--i);
  336.  
  337.     return (scp);
  338. #else
  339.     if (i && j)
  340.     return ((memalign_t) 0);
  341.     else
  342.     return ((memalign_t) 0);
  343. #endif
  344. }
  345.  
  346. #ifndef lint
  347. /* PWP: a bcopy that does overlapping extents correctly */
  348. static void
  349. mybcopy(from, to, len)
  350.     char   *from, *to;
  351.     register unsigned len;
  352. {
  353.     register char *sp, *dp;
  354.  
  355.     if (from == to)
  356.     return;
  357.     if (from < to) {
  358.     /* len is unsigned, len > 0 is equivalent to len != 0 */
  359.     for (sp = &from[len - 1], dp = &to[len - 1]; len != 0; len--, sp--, dp--)
  360.         *dp = *sp;
  361.     }
  362.     else {
  363.     /* len is unsigned, len > 0 is equivalent to len != 0 */
  364.     for (sp = from, dp = to; len != 0; len--, sp++, dp++)
  365.         *dp = *sp;
  366.     }
  367. }
  368.  
  369. #endif
  370.  
  371. /*
  372.  * When a program attempts "storage compaction" as mentioned in the
  373.  * old malloc man page, it realloc's an already freed block.  Usually
  374.  * this is the last block it freed; occasionally it might be farther
  375.  * back.  We have to search all the free lists for the block in order
  376.  * to determine its bucket: 1st we make one pass thru the lists
  377.  * checking only the first block in each; if that fails we search
  378.  * ``realloc_srchlen'' blocks in each list for a match (the variable
  379.  * is extern so the caller can modify it).  If that fails we just copy
  380.  * however many bytes was given to realloc() and hope it's not huge.
  381.  */
  382. #ifndef lint
  383. int     realloc_srchlen = 4;    /* 4 should be plenty, -1 =>'s whole list */
  384.  
  385. #endif                /* lint */
  386.  
  387. memalign_t
  388. realloc(cp, nbytes)
  389.     ptr_t   cp;
  390.     size_t  nbytes;
  391. {
  392. #ifndef lint
  393.     register U_int onb;
  394.     union overhead *op;
  395.     char   *res;
  396.     register int i;
  397.     int     was_alloced = 0;
  398.  
  399.     if (cp == NULL)
  400.     return (malloc(nbytes));
  401.     op = (union overhead *) (((caddr_t) cp) - MEMALIGN(sizeof(union overhead)));
  402.     if (op->ov_magic == MAGIC) {
  403.     was_alloced++;
  404.     i = op->ov_index;
  405.     }
  406.     else
  407.     /*
  408.      * Already free, doing "compaction".
  409.      * 
  410.      * Search for the old block of memory on the free list.  First, check the
  411.      * most common case (last element free'd), then (this failing) the last
  412.      * ``realloc_srchlen'' items free'd. If all lookups fail, then assume
  413.      * the size of the memory block being realloc'd is the smallest
  414.      * possible.
  415.      */
  416.     if ((i = findbucket(op, 1)) < 0 &&
  417.         (i = findbucket(op, realloc_srchlen)) < 0)
  418.     i = 0;
  419.  
  420.     onb = MEMALIGN(nbytes + MEMALIGN(sizeof(union overhead)) + RSLOP);
  421.  
  422.     /* avoid the copy if same size block */
  423.     if (was_alloced && (onb < (1 << (i + 3))) && (onb >= (1 << (i + 2))))
  424.     return ((memalign_t) cp);
  425.     if ((res = malloc(nbytes)) == NULL)
  426.     return (NULL);
  427.     if (cp != res)        /* common optimization */
  428.     mybcopy(cp, res, nbytes);
  429.     if (was_alloced)
  430.     free(cp);
  431.     return (res);
  432. #else
  433.     if (cp && nbytes)
  434.     return ((memalign_t) 0);
  435.     else
  436.     return ((memalign_t) 0);
  437. #endif                /* !lint */
  438. }
  439.  
  440.  
  441.  
  442. #ifndef lint
  443. /*
  444.  * Search ``srchlen'' elements of each free list for a block whose
  445.  * header starts at ``freep''.  If srchlen is -1 search the whole list.
  446.  * Return bucket number, or -1 if not found.
  447.  */
  448. static int
  449. findbucket(freep, srchlen)
  450.     union overhead *freep;
  451.     int     srchlen;
  452. {
  453.     register union overhead *p;
  454.     register int i, j;
  455.  
  456.     for (i = 0; i < NBUCKETS; i++) {
  457.     j = 0;
  458.     for (p = nextf[i]; p && j != srchlen; p = p->ov_next) {
  459.         if (p == freep)
  460.         return (i);
  461.         j++;
  462.     }
  463.     }
  464.     return (-1);
  465. }
  466.  
  467. #endif
  468.  
  469.  
  470. #else                /* SYSMALLOC */
  471.  
  472. /**
  473.  ** ``Protected versions'' of malloc, realloc, calloc, and free
  474.  **
  475.  ** On many systems:
  476.  **
  477.  ** 1. malloc(0) is bad
  478.  ** 2. free(0) is bad
  479.  ** 3. realloc(0, n) is bad
  480.  ** 4. realloc(n, 0) is bad
  481.  **
  482.  ** Also we call our error routine if we run out of memory.
  483.  **/
  484. memalign_t
  485. Malloc(n)
  486.     size_t  n;
  487. {
  488.     ptr_t   ptr;
  489.  
  490.     n = n ? n : 1;
  491.  
  492.     if ((ptr = malloc(n)) == (ptr_t) 0) {
  493.     child++;
  494.     stderror(ERR_NOMEM);
  495.     }
  496.     return ((memalign_t) ptr);
  497. }
  498.  
  499. memalign_t
  500. Realloc(p, n)
  501.     ptr_t   p;
  502.     size_t  n;
  503. {
  504.     ptr_t   ptr;
  505.  
  506.     n = n ? n : 1;
  507.     if ((ptr = (p ? realloc(p, n) : malloc(n))) == (ptr_t) 0) {
  508.     child++;
  509.     stderror(ERR_NOMEM);
  510.     }
  511.     return ((memalign_t) ptr);
  512. }
  513.  
  514. memalign_t
  515. Calloc(s, n)
  516.     size_t  s, n;
  517. {
  518.     char   *sptr;
  519.     ptr_t   ptr;
  520.  
  521.     n *= s;
  522.     n = n ? n : 1;
  523.     if ((ptr = malloc(n)) == (ptr_t) 0) {
  524.     child++;
  525.     stderror(ERR_NOMEM);
  526.     }
  527.  
  528.     sptr = (char *) ptr;
  529.     if (n != 0)
  530.     do
  531.         *sptr++ = 0;
  532.     while (--n);
  533.  
  534.     return ((memalign_t) ptr);
  535. }
  536.  
  537. void
  538. Free(p)
  539.     ptr_t   p;
  540. {
  541.     if (p)
  542.     free(p);
  543. }
  544.  
  545. #endif                /* SYSMALLOC */
  546.  
  547. /*
  548.  * mstats - print out statistics about malloc
  549.  *
  550.  * Prints two lines of numbers, one showing the length of the free list
  551.  * for each size category, the second showing the number of mallocs -
  552.  * frees for each size category.
  553.  */
  554. /*ARGSUSED*/
  555. void
  556. showall(v, c)
  557.     Char **v;
  558.     struct command *c;
  559. {
  560. #ifndef SYSMALLOC
  561.     register int i, j;
  562.     register union overhead *p;
  563.     int     totfree = 0, totused = 0;
  564.  
  565.     xprintf("tcsh current memory allocation:\nfree:\t");
  566.     for (i = 0; i < NBUCKETS; i++) {
  567.     for (j = 0, p = nextf[i]; p; p = p->ov_next, j++);
  568.     xprintf(" %4d", j);
  569.     totfree += j * (1 << (i + 3));
  570.     }
  571.     xprintf("\nused:\t");
  572.     for (i = 0; i < NBUCKETS; i++) {
  573.     xprintf(" %4d", nmalloc[i]);
  574.     totused += nmalloc[i] * (1 << (i + 3));
  575.     }
  576.     xprintf("\n\tTotal in use: %d, total free: %d\n",
  577.         totused, totfree);
  578.     xprintf("\tAllocated memory from 0x%lx to 0x%lx.  Real top at 0x%lx\n",
  579.         membot, memtop, (char *) sbrk(0));
  580. #else
  581.     xprintf("Allocated memory from 0x%lx to 0x%lx (%ld).\n",
  582.         membot, memtop = (char *) sbrk(0), memtop - membot);
  583. #endif                /* SYSMALLOC */
  584. }
  585.